import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 雷明浩
 * @date 2025/7/3 10:43
 */
public class PermuteUnique {
    // 有重复项数字的全排列
    // https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private ArrayList<ArrayList<Integer>> ret;
    private ArrayList<Integer> path;
    private boolean[] vis;
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        ret = new ArrayList<ArrayList<Integer>>();
        path = new ArrayList<>();
        vis = new boolean[num.length];
        Arrays.sort(num);
        dfs(num);
        return ret;
    }

    private void dfs(int[] num) {
        if (path.size() == num.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!vis[i]) {
                // 这里的判断是为了避免出现重复的排列
                if (i > 0 && num[i] == num[i-1] && !vis[i-1]) {
                    continue;
                } else {
                    vis[i] = true;
                    path.add(num[i]);
                    dfs(num);
                    vis[i] = false;
                    path.remove(path.size()-1);
                }
            }
        }
    }
}